class Solution { //leetcode——面试题08.07 三步问题
public:
    const int MOD=1e9+7;
    int waysToStep(int n) {
        //创建dp表,填充前三个数
        vector<int> dp {0,1,2,4};
        //状态方程为dp[n]=dp[n-1]+dp[n-2]+dp[n-3]
        if(n<=3){
            return dp[n];
        }
        int i=3;
        while(i<n){
            i++;
            dp.push_back(((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD);
        }
        return dp[n];
    }
};